package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/4/15 16:45
 */
public class C1781 {

    // https://leetcode-cn.com/problems/sum-of-beauty-of-all-substrings/
    // 一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。
    //
    //比方说，"abaacc" 的美丽值为 3 - 1 = 2 。
    //给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。
    public static int beautySum(String s) {
        char[] str = s.toCharArray();
        int ans = 0;
        for (int i = 0; i < str.length - 2; i++) {
            for (int j = i + 2; j < str.length; j++) {
                ans += compute(str, i, j);
            }
        }
        return ans;
    }

    static int[] count = new int[26];

    public static int compute(char[] str, int l, int r) {
        if (r - l < 2)
            return 0;
        for (int i = l; i <= r; i++)
            count[str[i] - 97]++;
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i : count) {
            max = Math.max(max, i);
            min = i > 0 ? Math.min(min, i) : min;
        }
        Arrays.fill(count, 0);
        System.out.println("l: " + l + "\t" + ", r: " + r + ", ans: " + (max - min));
        System.out.println("max: " + max + ", min: " + min);
        return min != 0 ? (max - min) : 0;
    }


    // for test
    public static void main(String[] args) {
        String str = "aabcb";
        System.out.println(beautySum(str));
    }

}
